Search Results

1. E. Hyytiä and J. Virtamo, Adaptive Importance Sampling in Routing and Wavelength Assignment, European Transactions on Telecommunications (ETT), vol. 13, no. 4, pp. 331-339, 2002, Special Issue on Rare Event Simulation (bib)

   Abstract: Dynamic routing and wavelength assignment in all-optical networks is a well-known problem for which many reasonably well working heuristic algorithms have been proposed in the literature. The problem can be also approached in the MDP framework. Due to the huge size of the state space only heuristic algorithms are viable in practice. However, so called first policy iteration can be used to enhance the performance of any given (standard) policy. In some cases the improvement can be considerable. For the first policy iteration one needs to estimate so called relative values of states, which are defined as the expected difference in future costs between two states. The relative values can be estimated by simulations starting the system from a given state. As the blocking probability in network is (usually) very low this leads to a problem where rare events must be estimated. Also, depending on the system's current state some arrival realisations are more likely to cause blockings than others. An adaptive importance sampling method is proposed to overcome these difficulties.